#include <iostream>

void Swap(int* x,int* y)
{
    int temp=*x;
    *x=*y;
    *y=temp;
}

void QuickSort(int *a,int left,int right)
{
    if(left>=right)
    {
        return ;
    }
    int begin = left;
	int end = right;
	//随机选keyi
	int randi = left + (rand() % (right - left));
	Swap(&a[left], &a[randi]);

    int keyi = left;
	int prev = left;
	int cur = left+1;

    while(cur<=right)
    {
        if(a[cur]<a[keyi])
        {
            prev++;
            Swap(&a[prev],&a[cur++]);
        }
        else
        {
            cur++;
        }
    }
    Swap(&a[prev], &a[keyi]);
	
	
	//递归左右子序列
	QuickSort(a, begin, prev - 1);
	QuickSort(a, prev + 1, end);
}

int main()
{
    int a[10]={5,3,6,9,7,1,0,2,4,10};
    QuickSort(a,0,9);
    for(int i=0;i<10;i++)
    {
        std::cout<<a[i]<<" ";
    }
    std::cout<<std::endl;
    return 0;
}